package interview.loop;

import interview.common.Node;
import interview.recursion.LinkedListCreator;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description: 循环
 * User: xxm
 * Date: 2018-02-20
 * Time: 21:42
 */
public class LinkedListReverser {

    /**
     * 逆置链表
     *
     * @param head head the linked list to reverse
     * @return reversed Linked List
     */
    public Node reverseLinkedList(Node head) {

        // newHead指向已经逆置的链表
        Node newHead = null;
        // curHead指向当前未逆置的链表
        Node curHead = head;

        while (curHead != null) {
            Node next = curHead.getNext();
            curHead.setNext(newHead);
            newHead = curHead;
            curHead = next;
        }
        return newHead;
    }

    public static void main(String[] args) {
        LinkedListReverser reverser = new LinkedListReverser();
        LinkedListCreator creator = new LinkedListCreator();

        Node.printLinkedList(reverser.reverseLinkedList(
                creator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5)))
        );
        Node.printLinkedList(reverser.reverseLinkedList(
                creator.createLinkedList(Arrays.asList(1)))
        );
        Node.printLinkedList(reverser.reverseLinkedList(
                creator.createLinkedList(new ArrayList<Integer>()))
        );
    }
}
